#include "myTree.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <functional> 

using namespace std;

TreeNode::TreeNode(char d,TreeNode* left,TreeNode* right,NodeTag lt,NodeTag rt){
    data=d;
    leftChild=left;
    rightChild=right;
    lTag=lt;
    rTag=rt;
}

TreeNode::~TreeNode(){

}

void TreeNode::printNode()
{
    cout << this->data;
}

MyTree::MyTree(){
    root=nullptr;
    isThread=false;
}

//辅助函数
TreeNode* buildnode(const char* pre,int& index){
    if(pre[index]=='@'||pre[index]=='\0'){
        index++;
        return nullptr;
    }
    char data=pre[index];
    index++;
    TreeNode* leftchild=buildnode(pre,index);
    TreeNode* rightchild=buildnode(pre,index);
    return new TreeNode(data,leftchild,rightchild,Link,Link);
}

MyTree::MyTree(const char pre[]){
    int index=0;
    root=buildnode(pre,index);
    isThread=false;
}

TreeNode* MyTree::copytree(TreeNode* node){
    if(node==nullptr){
        return nullptr;
    }
    TreeNode* newnode=new TreeNode(node->data,nullptr,nullptr,node->lTag,node->rTag);
    if(node->lTag==Link){
        newnode->leftChild=copytree(node->leftChild);
    }
    else{
        newnode->leftChild=node->leftChild;
    }
    if(node->rTag==Link){
        newnode->rightChild=copytree(node->rightChild);
    }
    else{
        newnode->rightChild=node->rightChild;
    }
    return newnode;
}

MyTree::MyTree(const MyTree& t){
    root=copytree(t.root);
    isThread=t.isThread;
}

void MyTree::deletree(TreeNode* node){
    if(node==nullptr){
        return;
    }
    if(node->lTag==Link&&node->leftChild!=nullptr){
        deletree(node->leftChild);
    }
    if(node->rTag==Link&&node->rightChild!=nullptr){
        deletree(node->rightChild);
    }
    delete node;
}

MyTree::~MyTree(){
    deletree(root);
    root=nullptr;
}

void MyTree::precheck(TreeNode* node){
    if(node==nullptr){
        return ;
    }
    node->printNode();
    
    if(node->lTag==Link){
        precheck(node->leftChild);
    }
    if(node->rTag==Link){
        precheck(node->rightChild);
    }
}

void MyTree::preOrderTraverse(){
    if(root==nullptr){
        return ;
    }
    precheck(root);
    //cout<<endl;
}

void MyTree::midcheck(TreeNode* node){
    if(node==nullptr){
        return ;
    }
    if(node->lTag==Link){
        midcheck(node->leftChild);
    }
    node->printNode();
    if(node->rTag==Link){
        midcheck(node->rightChild);
    }
}


// 线索二叉树中序遍历
void MyTree::inOrderThreaded() {
    if (root == nullptr) {
        return;
    }
    
    // 找到中序遍历的第一个节点（最左下的节点）
    TreeNode* current = root;
    while (current->lTag == Link && current->leftChild != nullptr) {
        current = current->leftChild;
    }
    
    // 沿着线索遍历所有节点
    while (current != nullptr) {
        // 访问当前节点
        current->printNode();
        
        // 如果右孩子是线索，直接跳转到后继节点
        if (current->rTag == Thread) {
            current = current->rightChild;
        } else {
            // 否则，找到右子树的最左下节点
            current = current->rightChild;
            if (current != nullptr) {
                 while (current->lTag == Link && current->leftChild != nullptr) {
                    current = current->leftChild;
                }
            }
        }
    }
}

void MyTree::inOrderTraverse(){
    if(root==nullptr){
        return ;
    }
    if(isThread){
        inOrderThreaded();
    }
    else{
        midcheck(root);
    }
}

void MyTree::backcheck(TreeNode* node){
    if(node==nullptr){
        return ;
    }
    if(node->lTag==Link&&node->leftChild!=nullptr){
        backcheck(node->leftChild);
    }
    if(node->rTag==Link&&node->rightChild!=nullptr){
        backcheck(node->rightChild);
    }
    node->printNode();
}

void MyTree::postOrderTraverse(){
    if(root==nullptr){
        return ;
    }
    backcheck(root);
    //cout<<endl;
}

TreeNode* MyTree::locatecheck(TreeNode* node,const char& v){
    if(node==nullptr){
        return nullptr;
    }
    if(node->data==v){
        return node;
    }
    TreeNode* left2=nullptr;
    if(node->lTag==Link&&node->leftChild!=nullptr){
        left2=locatecheck(node->leftChild,v);
        if(left2!=nullptr){
            return left2;
        }
    }
    TreeNode* right2=nullptr;
    if(node->rTag==Link&&node->rightChild!=nullptr){
        right2=locatecheck(node->rightChild,v);
        if(right2!=nullptr){
            return right2;
        }
    }
    return nullptr;
}

// 静态定义
static TreeNode notnode('\0', nullptr, nullptr, Link, Link);

TreeNode& MyTree::locateNode(const char& v){
     TreeNode* result = locatecheck(root, v);
    if (result != nullptr) {
        return *result;
    } else {
        //TreeNode* notfound('\0', nullptr, nullptr, Link, Link);
        return notnode;
    }
}

// 叶节点计数递归辅助函数
int MyTree::leafcheck(TreeNode* node){
    if(node==nullptr){
        return 0;
    }
    int count=0;
    if(((node->lTag==Thread)||(node->leftChild==nullptr))&&((node->rTag==Thread)||(node->rightChild==nullptr))){
        return 1;
    }
    if(node->lTag==Link&&node->leftChild!=nullptr){
        count+=leafcheck(node->leftChild);
    }
    if(node->rTag==Link&&node->rightChild!=nullptr){
        count+=leafcheck(node->rightChild);
    }
    return count;
}


//计算二叉树的叶子结点数
int MyTree::countLeaf() {
    if (root==nullptr) {
        return 0; 
    }
    
    return leafcheck(root);
}


int MyTree::highcheck(TreeNode* node){
    if(node==nullptr){
        return 0;
    }
    int leftheight=0;
    int rightheight=0;
    if(node->lTag==Link&&node->leftChild!=nullptr){
        leftheight=highcheck(node->leftChild);
    }
    if(node->rTag==Link&&node->rightChild!=nullptr){
        rightheight=highcheck(node->rightChild);
    }
    return (leftheight > rightheight ? leftheight : rightheight) + 1;
}


int MyTree::countHeight(){
    if(root==nullptr){
        return 0;
    }
    return highcheck(root);
}

bool MyTree::nodethread(TreeNode* node){
    if(node==nullptr){
        return false;
    }
    // 检查左标记
    if (node->lTag != Link && node->lTag != Thread) {
        return false; // 无效的标记值
    }
    
    // 检查右标记
    if (node->rTag != Link && node->rTag != Thread) {
        return false; // 无效的标记值
    }
    return (node->lTag==Thread)||(node->rTag==Thread);
}

bool MyTree::treethread(TreeNode* node){
    if(node==nullptr){
        return true;
    }
    if(!nodethread(node)){
        bool isleaf=(node->lTag==Thread||node->leftChild==nullptr)&&(node->rTag==Thread||node->rightChild==nullptr);
        if(!isleaf){
            return false;
        }
    }
    if(node->lTag==Link&&node->leftChild!=nullptr){
        if(!treethread(node->leftChild)){
            return false;
        }
    }
    if(node->rTag==Link&&node->rightChild!=nullptr){
        if(!treethread(node->rightChild)){
            return false;
        }
    }
    return true;
}

bool MyTree::isThreadedTree(){
    if(root==nullptr){
        return false;
    }
    if(isThread){
        return true;
    }
    if(treethread(root)){
        isThread=true;
        return true;
    }
    if(!treethread(root)){
        isThread=false;
        return false;
    }
}


void MyTree::inorderthreadcheck(TreeNode* node, TreeNode*& prev){
    if(node==nullptr){
        return ;
    }
    if(node->lTag==Link&&node->leftChild!=nullptr){
        inorderthreadcheck(node->leftChild,prev);
    }
    if(node->lTag==Thread||node->leftChild==nullptr){
        node->lTag=Thread;
        node->leftChild=prev;
    }
    if(prev!=nullptr&&(prev->rTag==Thread||prev->rightChild==nullptr)){
        prev->rTag=Thread;
        prev->rightChild=node;
    }
    prev=node;
    if(node->rTag==Link&&node->rightChild!=nullptr){
        inorderthreadcheck(node->rightChild,prev);
    }
}

bool MyTree::inOrderThreading(){
    if(isThread){
        return true;
    }
    if(root==nullptr){
        return false;
    }
    TreeNode* prev=nullptr;
    inorderthreadcheck(root,prev);
    // 处理最后一个节点的右线索（指向nullptr）
    if (prev!=nullptr&&(prev->rightChild==nullptr||prev->rTag==Thread)) {
        prev->rTag = Thread;
        prev->rightChild = nullptr;
    }
    isThread=true;
    return true;
}

// 定义全局静态空节点，用于返回无效的引用
static TreeNode nullNode('\0', nullptr, nullptr, Link, Link);

TreeNode& MyTree::preNode(const TreeNode& node){
    if(!isThread){
        return  nullNode;
    }
    if(node.lTag==Thread){
        if(node.leftChild!=nullptr) {
            return *node.leftChild;
        }else{
            return nullNode; 
        }
    }
    
    // 如果左标记是链接，则前驱节点是左子树中最右边的节点
    if (node.lTag==Link&&node.leftChild!=nullptr) {
        TreeNode* current=node.leftChild;
        
        // 找到左子树中最右边的节点（中序遍历的最后一个节点）
        while (current->rTag == Link && current->rightChild != nullptr) {
            current = current->rightChild;
        }
        
        return *current;
    }
    
    return nullNode;
}

// 寻找中序线索二叉树中某节点的后继节点
TreeNode& MyTree::nextNode(const TreeNode& node) {
    if(!isThread){
        return nullNode;
    }
    
    if(node.rTag==Thread){
        if(node.rightChild!=nullptr) {
            return *node.rightChild;
        } else{
            return nullNode; 
        }
    }
    
    if(node.rTag==Link&&node.rightChild!=nullptr) {
        TreeNode* current=node.rightChild;
        
        while(current->lTag==Link&&current->leftChild!=nullptr) {
            current=current->leftChild;
        }
        
        return *current;
    }
    return nullNode;
}

// 在 myTree.cpp 中实现 HuffmanTree 类的成员函数
HuffmanTree::HuffmanTree(const int& n, const int weights[]) {
    // 创建节点优先队列（最小堆）
    auto cmp = [](HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight; // 权重小的优先
    };
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, decltype(cmp)> minHeap(cmp);
    
    // 初始化叶子节点
    for (int i = 0; i < n; i++) {
        // 使用字符 'A' + i 作为节点标识，或者直接用权重值
        minHeap.push(new HuffmanNode(weights[i], 'A' + i));
    }
    
    // 构建霍夫曼树
    while (minHeap.size() > 1) {
        // 取出两个权重最小的节点
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();
                // 创建新节点，权重为两个子节点权重之和
        // 根据要求：偏小的值放左子树，偏大的值放右子树
        HuffmanNode* parent;
        if (left->weight <= right->weight) {
            parent = new HuffmanNode(left->weight + right->weight, left, right);
        } else {
            parent = new HuffmanNode(left->weight + right->weight, right, left);
        }
        
        minHeap.push(parent);
    }
    
    // 设置根节点
    if (!minHeap.empty()) {
        root = minHeap.top();
    } else {
        root = nullptr;
    }
    
    // 生成霍夫曼编码
    generateHuffmanCodes();
}
HuffmanTree::~HuffmanTree() {
    // 递归删除所有节点
    std::function<void(HuffmanNode*)> deleteTree = [&](HuffmanNode* node) {
        if (node) {
            deleteTree(node->left);
            deleteTree(node->right);
            delete node;
        }
    };
    deleteTree(root);
}
void HuffmanTree::generateHuffmanCodes() {
    huffmanCodes.clear();
    if (!root) return;
    
    // 使用DFS生成编码
    std::function<void(HuffmanNode*, std::string)> generateCodes = [&](HuffmanNode* node, std::string code) {
        if (!node) return;
        
        // 如果是叶子节点
        if (!node->left && !node->right) {
            huffmanCodes.push_back({node->weight, code});
            return;
        }
        
        // 递归处理左右子树
        if (node->left) {
            generateCodes(node->left, code + "0");
        }
        if (node->right) {
            generateCodes(node->right, code + "1");
        }
    };
    generateCodes(root, "");
    
    // 按节点值（重要度）递减排序
    std::sort(huffmanCodes.begin(), huffmanCodes.end(), 
              [](const std::pair<int, std::string>& a, const std::pair<int, std::string>& b) {
                  return a.first > b.first;
              });
}

void HuffmanTree::printHuffmanCodes() {
    for (const auto& codePair : huffmanCodes) {
        std::cout << codePair.first << ":" << codePair.second << std::endl;
    }
}